package com.cat.graphTheory;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/the-time-when-the-network-becomes-idle/description/
 * @create 2025/9/20 15:53
 * @since JDK17
 */

public class Solution18 {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.length, ans = 0, m = edges.length;
        List<Integer>[]g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        int[] dis = new int[n];
        Arrays.fill(dis, -1);
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            int from = edges[i][0], to = edges[i][1];
            g[from].add(to);
            g[to].add(from);
        }
        q.offer(0);
        dis[0] = 0;
        // 计算出每个点距离主服务器的路径
        while (!q.isEmpty()) {
            Integer x = q.poll();
            for (var y : g[x]) {
                if (dis[y] < 0) {
                    dis[y] = dis[x] + 1;
                    q.offer(y);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            int dist = dis[i] * 2;
            if (dist > dis[i]) {
                ans = Math.max(ans, (dist - 1) / patience[i] * patience[i] + dist);
            } else {
                ans = Math.max(ans, dist);
            }
        }

        return ans + 1;
    }
}
